package org.example.myleet.hashmap;

import org.example.myleet.Utils.Assert;
import org.example.myleet.Utils.JsonUtils;
import org.example.myleet.Utils.Parser;

import java.util.*;

public class HashMapSolution {

    //面试题 01.02. 判定是否互为字符重排
    public boolean CheckPermutation(String s1, String s2) {
        if (s1.length() != s2.length()) {
            return false;
        }
        Map<Character, Integer> s1CharCount = new HashMap<>(100);
        Map<Character, Integer> s2CharCount = new HashMap<>(100);
        char[] s1Char = s1.toCharArray();
        char[] s2Char = s2.toCharArray();
        int x = 0;
        for (char c : s1Char) {
            x ^= c;
            s1CharCount.put(c, s1CharCount.getOrDefault(c, 0) + 1);
        }
        for (char c : s2Char) {
            x ^= c;
            s2CharCount.put(c, s2CharCount.getOrDefault(c, 0) + 1);
        }
        if (x != 0) {
            return false;
        }
        for (Map.Entry<Character, Integer> entry : s1CharCount.entrySet()) {
            Integer s2CharCountNumber = s2CharCount.get(entry.getKey());
            if (null == s2CharCountNumber) {
                return false;
            }
            if (!s2CharCountNumber.equals(entry.getValue())) {
                return false;
            }
        }
        return true;
    }

    //面试题 01.08. 零矩阵
    public void setZeroes(int[][] matrix) {
        if (matrix.length < 1) {
            return;
        }
        int m = matrix.length, n = matrix[0].length;
        int[] rowSet = new int[m];
        int[] columnSet = new int[n];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] == 0) {
                    rowSet[i] = 1;
                    columnSet[j] = 1;
                }
            }
        }
        for (int i = 0; i < m; ++i) {
            if (rowSet[i] == 1) {
                for (int j = 0; j < n; ++j) {
                    matrix[i][j] = 0;
                }
            }
        }
        for (int j = 0; j < n; ++j) {
            if (columnSet[j] == 1) {
                for (int i = 0; i < m; ++i) {
                    matrix[i][j] = 0;
                }
            }
        }
    }

    //面试题 10.02. 变位词组
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> groups = new HashMap<>();
        for (String str : strs) {
            int[] freq = new int[26];
            for (int j = 0; j < str.length(); ++j) {
                ++freq[str.charAt(j) - 'a'];
            }
            StringBuilder tag = new StringBuilder();
            for (int f : freq) {
                tag.append(f);
            }
            String key = tag.toString();
            List<String> group = groups.getOrDefault(key, new ArrayList<>());
            group.add(str);
            groups.put(key, group);
        }
        return new ArrayList<>(groups.values());
    }

    //面试题 17.11. 单词距离
    public int findClosest(String[] words, String word1, String word2) {
        HashMap<String, List<Integer>> wordMapIdx = new HashMap<>();
        for (int i = 0; i < words.length; ++i) {
            String word = words[i];
            List<Integer> idxList = wordMapIdx.getOrDefault(word, new ArrayList<>());
            idxList.add(i);
            wordMapIdx.put(word, idxList);
        }
        List<Integer> word1IdxList = wordMapIdx.get(word1);
        List<Integer> word2IdxList = wordMapIdx.get(word2);
        int minDist = Integer.MAX_VALUE, n1 = word1IdxList.size(), n2 = word2IdxList.size();
        for (int i1 = 0; i1 < n1; ++i1) {
            int prevDist = Math.abs(word1IdxList.get(i1) - word2IdxList.get(0));
            if (prevDist < minDist) {
                minDist = prevDist;
            }
            for (int i2 = 1; i2 < n2; ++i2) {
                int curDist = Math.abs(word1IdxList.get(i1) - word2IdxList.get(i2));
                if (curDist < minDist) {
                    minDist = curDist;
                }
                if (curDist > prevDist) {
                    break;
                }
            }
        }
        return minDist;
    }

    //p1
    public int[] twoSum(int[] nums, int target) {
        //缓存另一半结果，复杂度为n，3ms
        Map<Integer, Integer> oppositeMap = new HashMap<>(nums.length);
        for (int i=0; i<nums.length; i++) {
            if (oppositeMap.containsKey(nums[i])) {
                //找到另一半结果，i即第二个位置，第一个位置是缓存的位置
                int first = oppositeMap.get(nums[i]);
                if (first != i) {
                    return new int[]{first, i};
                }
            }
            //计算另一半，缓存这个位置
            int opposite = target - nums[i];
            oppositeMap.put(opposite, i);
        }
        return new int[0];
    }

    //p30
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> result = new ArrayList<>();
        Map<String, Integer> wordMapCount = new HashMap<>(words.length);
        int wordLen = words[0].length();
        int windowLen = 0;
        int[] wordCharCount = new int[26];
        for (String word : words) {
            for (char c : word.toCharArray()) {
                ++wordCharCount[c - 'a'];
                ++windowLen;
            }
            wordMapCount.put(word, wordMapCount.getOrDefault(word, 0) + 1);
        }
        if (s.length() < windowLen) {
            return result;
        }
        int[] windowCharCount = new int[26];
        int i = 0;
        for (; i < windowLen; ++i) {
            char c = s.charAt(i);
            ++windowCharCount[c - 'a'];
        }
        int end = s.length() + 1;
        while (i < end) {
            int idx = i - windowLen;
            if (isCountIdentical(windowCharCount, wordCharCount)) {
                boolean found = true;
                Map<String, Integer> wordCount = new HashMap<>();
                for (int j = 0; j < words.length; ++j) {
                    String sub = s.substring(idx + j * wordLen, idx + (j + 1) * wordLen);
                    if (!wordMapCount.containsKey(sub)) {
                        found = false;
                        break;
                    }
                    wordCount.put(sub, wordCount.getOrDefault(sub, 0) + 1);
                }
                if (found && isCountIdentical(wordMapCount, wordCount)) {
                    result.add(idx);
                }
            }
            char cLeft = s.charAt(idx);
            --windowCharCount[cLeft - 'a'];
            if (i < s.length()) {
                char cRight = s.charAt(i);
                ++windowCharCount[cRight - 'a'];
            }
            ++i;
        }
        return result;
    }
    private boolean isCountIdentical(int[] windowCharCount, int[] wordCharCount) {
        for (int i = 0; i < 26; ++i) {
            if (windowCharCount[i] != wordCharCount[i]) {
                return false;
            }
        }
        return true;
    }
    private boolean isCountIdentical(Map<String, Integer> wordMapCount1, Map<String, Integer> wordMapCount2) {
        if (wordMapCount1.size() != wordMapCount2.size()) {
            return false;
        }
        for (Map.Entry<String, Integer> entry : wordMapCount1.entrySet()) {
            Integer count2 = wordMapCount2.get(entry.getKey());
            if (!entry.getValue().equals(count2)) {
                return false;
            }
        }
        return true;
    }

    //p36
    /**
     * 官方解，哈希法
     */
    public boolean isValidSudoku(char[][] board) {
        int[][] verticalHash = new int[9][10];
        int[][] horizontalHash = new int[9][10];
        int[][][] gridHash = new int[3][3][10];
        for (int r = 0; r < 9; ++r) {
            for (int c = 0; c < 9; ++c) {
                char character = board[r][c];
                if (character != '.') {
                    int i = character - '0';
                    ++verticalHash[c][i];
                    ++horizontalHash[r][i];
                    int y = r / 3, x = c / 3;
                    ++gridHash[y][x][i];
                    if (verticalHash[c][i] > 1 || horizontalHash[r][i] > 1 || gridHash[y][x][i] > 1) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
    private boolean isValidSudoku2(char[][] board) {
        for (int r = 0; r < 9; ++r) {
            for (int c = 0; c < 9; ++c) {
                if (board[r][c] != '.' && !valid(board, r, c)) {
                    return false;
                }
            }
        }
        return true;
    }
    /**
     * 判断board中，r行c列的数字是否有效，按照数独规则就是r行、c列以及r行c列所在的小九宫格数字不会重复
     */
    private boolean valid(char[][] board, int r, int c) {
        char number = board[r][c];
        //检查一列中是否有重复
        for (int i = 0; i < 9; ++i) {
            if (i != r && number == board[i][c]) {
                return false;
            }
        }
        //检查一行中是否有重复
        for (int j = 0; j < 9; ++j) {
            if (j != c && number == board[r][j]) {
                return false;
            }
        }
        //检查r、c所在九宫格中是否有重复
        int r_ = r / 3 * 3;
        int c_ = c / 3 * 3;
        for (int i = r_; i < r_ + 3; ++i) {
            for (int j = c_; j < c_ + 3; ++j) {
                if (i != r && j != c && number == board[i][j]) {
                    return false;
                }
            }
        }
        return true;
    }

    //p49【哈希表】字母异位词分组
    public List<List<String>> groupAnagrams49(String[] strs) {
        Map<Integer, List<String>> hashValMapAnagrams = new HashMap<>();
        for (int i = 0; i < strs.length; i++) {
            String word = strs[i];
            int[] alphabetCount = new int[26];
            //单词统计各字母频数
            for (int j = 0; j < word.length(); j++){
                ++alphabetCount[word.charAt(j) - 'a'];
            }
            int hashValue = 0;
            for (int j = 0; j < 26; ++j) {
                hashValue = (hashValue * 29) + alphabetCount[j];
            }
            List<String> anagrams = hashValMapAnagrams.getOrDefault(hashValue, new LinkedList<>());
            anagrams.add(word);
            hashValMapAnagrams.put(hashValue, anagrams);
        }
        return new LinkedList<>(hashValMapAnagrams.values());
    }

    /**
     * 205【哈希表】同构字符串
     * O(n)
     * 5 ms
     */
    public boolean isIsomorphic(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        if (s.length() == 0) {
            return true;
        }
        int[] sReflection = new int[128];
        int[] tReflection = new int[128];
        for (int i = 0; i < 128; i++) {
            sReflection[i] = -1;
            tReflection[i] = -1;
        }
        for (int i = 0; i < s.length(); i++) {
            char sc = s.charAt(i);
            char tc = t.charAt(i);
            if (sReflection[sc] < 0) {
                sReflection[sc] = tc;
            } else {
                if (sReflection[sc] != tc) {
                    return false;
                }
            }
            if (tReflection[tc] < 0) {
                tReflection[tc] = sc;
            } else {
                if (tReflection[tc] != sc) {
                    return false;
                }
            }
        }
        return true;
    }

    /**
     * 219【哈希表】存在重复元素 II
     */
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        if (k == 0) return false;
        int n = nums.length;
        HashSet<Integer> set = new HashSet<>(k + 1);
        for (int i = 0; i < k; ++i) {
            if (i >= n) return false;
            if (!set.add(nums[i])) return true;
        }
        for (int i = k; i < n; ++i) {
            if (!set.add(nums[i])) return true;
            set.remove(nums[i - k]);
        }
        return false;
    }

    /**
     * 242【哈希表】有效的字母异位词
     */
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        int[] charCount = new int[128];
        for (int i = 0; i < s.length(); i++) {
            ++charCount[s.charAt(i)];
            --charCount[t.charAt(i)];
        }
        for (int i = 0; i < 128; i++) {
            if (charCount[i] != 0) {
                return false;
            }
        }
        return true;
    }

    /**
     * 290【哈希表】单词规律
     * 没什么技巧，就是判断模式的字符代号能不能匹配对应单词
     * O(n)
     * 1 ms
     */
    public boolean wordPattern(String pattern, String s) {
        char[] patternChars = pattern.toCharArray();
        //字母匹配单词
        Map<Character, String> patternCharWordMap = new HashMap<>(patternChars.length);
        //单词匹配字母
        Map<String, Character> wordPatternCharMap = new HashMap<>(patternChars.length);
        String[] words = s.split(" ");
        if (patternChars.length != words.length) {
            return false;
        }
        for (int i=0; i<words.length; i++) {
            if (patternCharWordMap.containsKey(patternChars[i])) {
                //存在字母与单词匹配关系，检查当前位置字母与当前位置单词是否匹配
                String patterWord = patternCharWordMap.get(patternChars[i]);
                if (!patterWord.equalsIgnoreCase(words[i])) {
                    return false;
                }
            } else if (wordPatternCharMap.containsKey(words[i])) {
                //存在字母与单词匹配关系，检查当前位置字母与当前位置单词是否匹配
                Character c = wordPatternCharMap.get(words[i]);
                if (patternChars[i] != c) {
                    return false;
                }
            } else {
                //不存在字母与单词匹配关系，加入对应关系
                patternCharWordMap.put(patternChars[i], words[i]);
                wordPatternCharMap.put(words[i], patternChars[i]);
            }
        }
        return true;
    }

    /**
     * 299【哈希表+计数】猜数字游戏
     */
    public String getHint(String secret, String guess) {
        int bull = 0, cow = 0;
        int[] count = new int[10];
        char[] secretCharArr = secret.toCharArray();
        char[] guessCharArr = guess.toCharArray();
        for (char s : secretCharArr) {
            //先统计secret中的数字频数
            ++count[s - '0'];
        }
        for (int i = 0; i < secret.length(); ++i) {
            char s = secretCharArr[i];
            char g = guessCharArr[i];
            int sid = s - '0';
            if (s == g) {
                //i位置上相同，代表公牛，减去一个匹配，如果匹配数不够，减去一个奶牛（一定是被别的奶牛抢了这个公牛匹配）
                if (count[sid] > 0) {
                    --count[s - '0'];
                } else {
                    --cow;
                }
                ++bull;
            } else {
                //i位置上不同
                int gid = g - '0';
                if (count[gid] > 0) {
                    //guessCharArr[i]对应的字符在secretCharArr上还能找到匹配，代表奶牛，减去一个匹配
                    --count[gid];
                    ++cow;
                }
            }
        }
        return new StringBuilder().append(bull).append('A').append(cow).append('B').toString();
    }

    /**
     * 349【哈希表】两个数组的交集
     */
    public int[] intersection(int[] nums1, int[] nums2) {
        if (0 == nums1.length || 0 == nums2.length) {
            //其中一个是空的就是空的
            return new int[0];
        }
        //保存结果
        Set<Integer> result = new HashSet<>(nums1.length);
        //保存第一个数组中的数字出现情况
        Set<Integer> num1Set = new HashSet<>();
        for (int num : nums1) {
            num1Set.add(num);
        }
        for (int num : nums2) {
            if (num1Set.contains(num)) {
                //如果第二个数组中的数字出现在第一个数组中，算交集，如果重复出现算1个
                result.add(num);
            }
        }
        int i = 0;
        int[] answer = new int[result.size()];
        for (int num : result) {
            //复制结果到数组中
            answer[i] = num;
            ++i;
        }
        return answer;
    }

    /**
     * 380【哈希表】O(1) 时间插入、删除和获取随机元素
     */
    static class RandomizedSet {

        private Random rand;
        private ArrayList<Integer> numberList;
        private HashMap<Integer, Integer> numberMap;

        public RandomizedSet() {
            rand = new Random(System.currentTimeMillis());
            numberMap = new HashMap<>();
            numberList = new ArrayList<>();
        }

        public boolean insert(int val) {
            if (numberMap.containsKey(val)) {
                return false;
            }
            numberList.add(val);
            numberMap.put(val, numberList.size() - 1);
            return true;
        }

        public boolean remove(int val) {
            Integer i = numberMap.get(val);
            if (null == i) {
                return false;
            }
            int last = numberList.get(numberList.size() - 1);
            numberList.set(i, last);
            numberMap.put(last, i);
            numberList.remove(numberList.size() - 1);
            numberMap.remove(val);
            return true;
        }

        public int getRandom() {
            return numberList.get(rand.nextInt(numberList.size()));
        }
    }

    /**
     * 383【哈希表+计数】赎金信
     */
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] ransomLetterCount = new int[26];
        int[] magazineLetterCount = new int[26];
        for (char c : ransomNote.toCharArray()) {
            ++ransomLetterCount[c - 'a'];
        }
        for (char c : magazine.toCharArray()) {
            ++magazineLetterCount[c - 'a'];
        }
        for (int i = 0; i < 26; ++i) {
            if (magazineLetterCount[i] < ransomLetterCount[i]) {
                return false;
            }
        }
        return true;
    }

    /**
     * 447【哈希表】回旋镖的数量
     * 思路：题目要的是从某个点出发，到其余各个点形成的边，当遇到其余两个点长度相同的时候，可以组成2个回旋镖形状（直线也算）。
     * 可以转换成收集一个点发出的所有边，按长度归类，先用哈希表做边的长度归类，因为只考虑边的长度，因此直接统计数字就可以，
     * 对于某种边长，如果存在边数x>1，说明可以从x条边中不放回任意取出2条组成回旋镖，总的排列组合数为x*(x-1)
     * 需要针对每个点做一次上述工作，因此复杂度为O(n^2)
     */
    public int numberOfBoomerangs(int[][] points) {
        int n = points.length, answer = 0;
        if (n < 3) return 0;
        for (int i = 0; i < n; ++i) {
            int[] pi = points[i];
            //边的长度归类哈希表
            Map<Integer, Integer> d2size = new HashMap<>();
            for (int j = 0; j < n; ++j) {
                if (i == j) continue;
                int[] pj = points[j];
                //计算欧氏距离
                int dx = pi[0] - pj[0];
                int dy = pi[1] - pj[1];
                int d = dx * dx + dy * dy;
                //归类边的长度
                d2size.put(d, d2size.getOrDefault(d, 0) + 1);
            }
            for (Map.Entry<Integer, Integer> entry : d2size.entrySet()) {
                int x = entry.getValue();
                //计算取出2条边的排列数
                answer += x * (x - 1);
            }
        }
        return answer;
    }

    //p1048
    public int longestStrChain(String[] words) {
        Set<String>[] lenMapWordSet = new HashSet[17];
        for (int i = 0; i <= 16; ++i) {
            lenMapWordSet[i] = new HashSet<>();
        }
        Map<String, Integer> wordMapChainLen = new HashMap<>();
        int wordLen = 0;
        for (String word : words) {
            wordLen = Math.max(wordLen, word.length());
            wordMapChainLen.put(word, 1);
            Set<String> wordSet = lenMapWordSet[word.length()];
            wordSet.add(word);
        }
        int answer = 1;
        while(wordLen > 1) {
            Set<String> wordSet = lenMapWordSet[wordLen];
            Set<String> wordSetS1 = lenMapWordSet[wordLen - 1];
            if (!wordSet.isEmpty() && !wordSetS1.isEmpty()) {
                for (String word : wordSet) {
                    int wordChainLen = wordMapChainLen.get(word);
                    char[] charArr = word.toCharArray();
                    StringBuilder sb = new StringBuilder();
                    sb.append(word);
                    for (int i = 0; i < charArr.length; ++i) {
                        char c = charArr[i];
                        sb.deleteCharAt(i);
                        String s1 = sb.toString();
                        if (wordSetS1.contains(s1)) {
                            int s1ChainLen = wordChainLen + 1;
                            answer = Math.max(answer, s1ChainLen);
                            if (s1ChainLen > wordMapChainLen.get(s1)) {
                                wordMapChainLen.put(s1, s1ChainLen);
                            }
                        }
                        sb.insert(i, c);
                    }
                }
            }
            --wordLen;
        }
        return answer;
    }

    //p1138
    public String alphabetBoardPath(String target) {
        int[][] charMapPoint = new int['z' + 1][2];
        for (int i = 0; i < 26; ++i) {
            char ch = (char) ('a' + i);
            charMapPoint[ch] = new int[]{i / 5, i % 5};
        }
        StringBuilder answer = new StringBuilder();
        int[] prevPoint = new int[]{0, 0};
        char prevChar = 'a';
        for (int i = 0; i < target.length(); ++i) {
            char curChar = target.charAt(i);
            boolean z = false;
            if (prevChar != curChar && curChar == 'z') {
                z = true;
                curChar = 'u';
            }
            int[] curPoint = charMapPoint[curChar];
            //move up or down
            if (prevPoint[0] > curPoint[0]) {
                int m = prevPoint[0] - curPoint[0];
                for (int j = 0; j < m; ++j) {
                    answer.append('U');
                }
            } else if (prevPoint[0] < curPoint[0]) {
                int m = curPoint[0] - prevPoint[0];
                for (int j = 0; j < m; ++j) {
                    answer.append('D');
                }
            }
            //move left or right
            if (prevPoint[1] > curPoint[1]) {
                int m = prevPoint[1] - curPoint[1];
                for (int j = 0; j < m; ++j) {
                    answer.append('L');
                }
            } else if (prevPoint[1] < curPoint[1]) {
                int m = curPoint[1] - prevPoint[1];
                for (int j = 0; j < m; ++j) {
                    answer.append('R');
                }
            }
            prevPoint = curPoint;
            prevChar = curChar;
            if (z) {
                answer.append('D');
                prevPoint = charMapPoint['z'];
                prevChar = 'z';
            }
            answer.append('!');
        }
        return answer.toString();
    }

    //p1604
    public List<String> alertNames(String[] keyName, String[] keyTime) {
        Map<String, List<Integer>> nameMapTimes = new HashMap<>();
        for (int i = 0; i < keyTime.length; ++i) {
            List<Integer> times = nameMapTimes.getOrDefault(keyName[i], new ArrayList<>());
            times.add(Integer.parseInt(keyTime[i].substring(0, 2)) * 60 + Integer.parseInt(keyTime[i].substring(3, 5)));
            nameMapTimes.put(keyName[i], times);
        }
        Set<String> warnings = new HashSet<>();
        for (Map.Entry<String, List<Integer>> entry : nameMapTimes.entrySet()) {
            List<Integer> times = entry.getValue();
            if (times.size() < 3) continue;
            times.sort(Comparator.naturalOrder());
            int prevPrev = times.get(0);
            int prev = times.get(1);
            for (int j = 2; j < times.size(); ++j) {
                int t = times.get(j);
                if (t - prevPrev <= 60) {
                    warnings.add(entry.getKey());
                    break;
                }
                prevPrev = prev;
                prev = t;
            }
        }
        List<String> answer = new ArrayList<>(warnings);
        answer.sort(Comparator.naturalOrder());
        return answer;
    }

    //1615
    public int maximalNetworkRank(int n, int[][] roads) {
        Map<Integer, Integer> nodeMapEdgeCount = new HashMap<>(n);
        Map<Integer, Set<Integer>> nodeMapOtherNodeSet = new HashMap<>(n);
        for (int[] road : roads) {
            int a = road[0];
            int b = road[1];
            nodeMapEdgeCount.put(a, nodeMapEdgeCount.getOrDefault(a, 0) + 1);
            nodeMapEdgeCount.put(b, nodeMapEdgeCount.getOrDefault(b, 0) + 1);
            Set<Integer> otherNodeSet = nodeMapOtherNodeSet.getOrDefault(a, new HashSet<>());
            otherNodeSet.add(b);
            nodeMapOtherNodeSet.put(a, otherNodeSet);
            otherNodeSet = nodeMapOtherNodeSet.getOrDefault(b, new HashSet<>());
            otherNodeSet.add(a);
            nodeMapOtherNodeSet.put(b, otherNodeSet);
        }
        int answer = 0;
        for (int i = 0; i < n - 1; ++i) {
            for (int j = i + 1; j < n; ++j) {
                int rank = nodeMapEdgeCount.getOrDefault(i, 0) + nodeMapEdgeCount.getOrDefault(j, 0);
                if (nodeMapOtherNodeSet.getOrDefault(i, new HashSet<>()).contains(j) || nodeMapOtherNodeSet.getOrDefault(j, new HashSet<>()).contains(i)) {
                    --rank;
                }
                answer = Math.max(answer, rank);
            }
        }
        return answer;
    }

    /**
     * 1726【哈希统计】同积元组
     */
    public int tupleSameProduct(int[] nums) {
        int n = nums.length;
        //记录乘积出现的次数
        Map<Integer, Integer> productMapCnt = new HashMap<>();
        int answer = 0;
        for (int i = 0; i < n; ++i) {
            int a = nums[i];
            for (int j = i + 1; j < n; ++j) {
                int product = a * nums[j];
                //找出乘积出现的次数，每个乘积代表一对独一无二的数，每一对数可以和当前的a*b组合在一起形成一个新的四元组
                int productCnt = productMapCnt.getOrDefault(product, 0);
                //每个四元组由于四个数字都不相同，因此有8种排列组合：A(2,2) * A(2,2) * 2 = 8，两个数在左边排列 * 两个数在右边排列 * 两对数交换过来
                answer += productCnt * 8;
                ++productCnt;
                productMapCnt.put(product, productCnt);
            }
        }
        return answer;
    }

    //p1781
    public int beautySum(String s) {
        int sumScore = 0;
        Map<Character, Integer> charMapCount;
        TreeMap<Integer, Set<Character>> countMapChars;
        for (int i = 3; i <= s.length(); ++i) {
            //init
            charMapCount = new HashMap<>();
            countMapChars = new TreeMap<>(Comparator.naturalOrder());
            for (int j = 0; j < i; ++j) {
                char ch = s.charAt(j);
                int prevCount = charMapCount.getOrDefault(ch, 0);
                if (prevCount > 0) {
                    Set<Character> chars = countMapChars.get(prevCount);
                    chars.remove(ch);
                    if (chars.isEmpty()) {
                        countMapChars.remove(prevCount);
                    }
                }
                int newCount = prevCount + 1;
                Set<Character> chars = countMapChars.getOrDefault(newCount, new HashSet<>());
                chars.add(ch);
                countMapChars.put(newCount, chars);
                charMapCount.put(ch, newCount);
            }
            int min = countMapChars.firstKey();
            int max = countMapChars.lastKey();
            sumScore += max - min;
            for (int j = i; j < s.length(); ++j) {
                //remove char
                char removeCh = s.charAt(j - i);
                int prevCount = charMapCount.getOrDefault(removeCh, 0);
                Set<Character> chars = countMapChars.get(prevCount);
                if (null == chars) {
                    System.out.println("fuck");
                }
                chars.remove(removeCh);
                if (chars.isEmpty()) {
                    countMapChars.remove(prevCount);
                }
                int newCount = prevCount - 1;
                if (newCount > 0) {
                    chars = countMapChars.getOrDefault(newCount, new HashSet<>());
                    chars.add(removeCh);
                    countMapChars.put(newCount, chars);
                }
                charMapCount.put(removeCh, newCount);
                //add char
                char addCh = s.charAt(j);
                prevCount = charMapCount.getOrDefault(addCh, 0);
                if (prevCount > 0) {
                    chars = countMapChars.get(prevCount);
                    chars.remove(addCh);
                    if (chars.isEmpty()) {
                        countMapChars.remove(prevCount);
                    }
                }
                newCount = prevCount + 1;
                chars = countMapChars.getOrDefault(newCount, new HashSet<>());
                chars.add(addCh);
                countMapChars.put(newCount, chars);
                charMapCount.put(addCh, newCount);
                min = countMapChars.firstKey();
                max = countMapChars.lastKey();
                sumScore += max - min;
            }
        }
        return sumScore;
    }

    //p1797
    static class AuthenticationManager {
        private int ttl;
        private Map<String, Integer> tokenMapTime;
        private TreeMap<Integer, String> timeMapToken;
        public AuthenticationManager(int timeToLive) {
            ttl = timeToLive;
            tokenMapTime = new HashMap<>();
            timeMapToken = new TreeMap<>(Comparator.naturalOrder());
        }
        public void generate(String tokenId, int currentTime) {
            tokenMapTime.put(tokenId, currentTime);
            timeMapToken.put(currentTime, tokenId);
        }
        public void renew(String tokenId, int currentTime) {
            removeExpired(currentTime);
            Integer time = tokenMapTime.get(tokenId);
            if (null != time) {
                timeMapToken.remove(time);
                timeMapToken.put(currentTime, tokenId);
                tokenMapTime.put(tokenId, currentTime);
            }
        }
        public int countUnexpiredTokens(int currentTime) {
            removeExpired(currentTime);
            return tokenMapTime.size();
        }
        private void removeExpired(int currentTime) {
            int prevTime = currentTime - ttl;
            Integer expiredTime = timeMapToken.floorKey(prevTime);
            if (null == expiredTime) {
                return;
            }
            List<Integer> timeToBeRemove = new LinkedList<>();
            for (int time : timeMapToken.navigableKeySet()) {
                if (time <= expiredTime) {
                    timeToBeRemove.add(time);
                    String token = timeMapToken.get(time);
                    tokenMapTime.remove(token);
                } else {
                    break;
                }
            }
            for (int time : timeToBeRemove) {
                timeMapToken.remove(time);
            }
        }
    }

    //p1807
    public String evaluate(String s, List<List<String>> knowledge) {
        Map<String, String> knowledgeMap = new HashMap<>(knowledge.size());
        for (List<String> kv : knowledge) {
            knowledgeMap.put(kv.get(0), kv.get(1));
        }
        StringBuilder result = new StringBuilder();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); ++i) {
            char ch = s.charAt(i);
            if (ch == '(') {
                while (i < s.length() - 1 && ch != ')') {
                    ++i;
                    ch = s.charAt(i);
                    sb.append(ch);
                }
                sb.deleteCharAt(sb.length() - 1);
                String value = knowledgeMap.get(sb.toString());
                if (null != value) {
                    result.append(value);
                } else {
                    result.append("?");
                }
                sb = new StringBuilder();
            } else {
                result.append(ch);
            }
        }
        return result.toString();
    }

    //p1814
    public int countNicePairs(int[] nums) {
        int MOD = 1000000007;
        Map<Integer, Integer> diffCountMap = new HashMap<>(nums.length);
        for (int n : nums) {
            int num = n;
            int r = 0;
            while (num > 0) {
                r *= 10;
                r += (num - num / 10 * 10);
                num /= 10;
            }
            int diff = r - n;
            diffCountMap.put(diff, diffCountMap.getOrDefault(diff, 0) + 1);
        }
        long sum = 0;
        for (Map.Entry<Integer, Integer> entry : diffCountMap.entrySet()) {
            if (entry.getValue() > 1) {
                sum += (long) entry.getValue() * (entry.getValue() - 1) / 2;
                sum %= MOD;
            }
        }
        return (int) sum;
    }

    //p1817
    public int[] findingUsersActiveMinutes(int[][] logs, int k) {
        Map<Integer, Set<Integer>> userMapActiveTime = new HashMap<>();
        for (int[] log : logs) {
            Set<Integer> activeTime = userMapActiveTime.getOrDefault(log[0], new HashSet<>());
            activeTime.add(log[1]);
            userMapActiveTime.put(log[0], activeTime);
        }
        int[] answer = new int[k];
        for (Map.Entry<Integer, Set<Integer>> entry : userMapActiveTime.entrySet()) {
            int time = entry.getValue().size();
            ++answer[time - 1];
        }
        return answer;
    }

    //p2006
    public int countKDifference(int[] nums, int k) {
        int count = 0, target;
        //散列表，记录num出现了多少次
        int[] numCount = new int[101];
        for (int num : nums) {
            ++numCount[num];
            //target是和num相差k的值，找出已经出现了多少个就知道有多少对
            target = num - k;
            if (target > 0) {
                count += numCount[target];
            }
            target = num + k;
            if (target < 101) {
                count += numCount[target];
            }
        }
        return count;
    }
//    public int countKDifference(int[] nums, int k) {
//        int count = 0;
//        for (int i = 0; i < nums.length; ++i) {
//            for (int j = i + 1; j < nums.length; ++j) {
//                if (Math.abs(nums[i] - nums[j]) == k) {
//                    ++count;
//                }
//            }
//        }
//        return count;
//    }

    //p2013
    static class DetectSquares {

        static class Point {
            int[] point;
            int pointCount;

            public Point(int[] point) {
                this.point = point;
                pointCount = 0;
            }

            public static int getPointHash(int[] point) {
                return point[0] * 10000 + point[1];
            }

            public static int getPointHash(int x, int y) {
                return x * 10000 + y;
            }
        }

        private HashMap<Integer, Point> pointCountMap;

        public DetectSquares() {
            pointCountMap = new HashMap<>(1000);
        }

        public void add(int[] point) {
            int pointHash = Point.getPointHash(point);
            Point p = pointCountMap.computeIfAbsent(pointHash, key -> new Point(point));
            ++p.pointCount;
        }

        public int count(int[] point) {
            int result = 0;
            for (Point p : pointCountMap.values()) {
                //扫描每一个点，寻找可能成为正方形的对角点
                if (point[0] == p.point[0] || point[1] == p.point[1] || Math.abs(point[0] - p.point[0]) != Math.abs(point[1] - p.point[1])) {
                    //p与point共点或共轴，或长宽不相等，都不能成为正方形，略过
                    continue;
                }
                Point p1, p2;
                //考虑p在point的对角形成矩形的可能性
                p1 = pointCountMap.get(Point.getPointHash(point[0], p.point[1]));
                p2 = pointCountMap.get(Point.getPointHash(p.point[0], point[1]));
                if (p1 != null && p2 != null) {
                    //另外3点（p、p1、p2）都存在，说明矩形存在，计算可能方案
                    result += p.pointCount * p1.pointCount * p2.pointCount;
                }
            }
            return result;
        }
    }

    //p2032
    public List<Integer> twoOutOfThree(int[] nums1, int[] nums2, int[] nums3) {
        Set<Integer> result = new HashSet<>(200);
        Set<Integer> set1 = new HashSet<>(nums1.length);
        for (int num : nums1) {
            set1.add(num);
        }
        Set<Integer> set2 = new HashSet<>(nums2.length);
        for (int num : nums2) {
            set2.add(num);
        }
        Set<Integer> set3 = new HashSet<>(nums3.length);
        for (int num : nums3) {
            set3.add(num);
        }
        for (int num : nums1) {
            if (set2.contains(num)) {
                result.add(num);
            } else if (set3.contains(num)) {
                result.add(num);
            }
        }
        for (int num : nums2) {
            if (set1.contains(num)) {
                result.add(num);
            } else if (set3.contains(num)) {
                result.add(num);
            }
        }
        for (int num : nums3) {
            if (set1.contains(num)) {
                result.add(num);
            } else if (set2.contains(num)) {
                result.add(num);
            }
        }
        return new ArrayList<>(result);
    }

    //p2043
    static class Bank2043 {
        private long[] balance;

        public Bank2043(long[] balance) {
            this.balance = balance;
        }

        public boolean transfer(int account1, int account2, long money) {
            if (account1 > balance.length || account2 > balance.length) {
                return false;
            }
            int i1 = account1 - 1;
            int i2 = account2 - 1;
            if (balance[i1] < money) {
                return false;
            }
            balance[i1] -= money;
            balance[i2] += money;
            return true;
        }

        public boolean deposit(int account, long money) {
            if (account > balance.length) {
                return false;
            }
            balance[account - 1] += money;
            return true;
        }

        public boolean withdraw(int account, long money) {
            if (account > balance.length) {
                return false;
            }
            int i = account - 1;
            if (balance[i] < money) {
                return false;
            }
            balance[i] -= money;
            return true;
        }
    }

    //p2287
    public int rearrangeCharacters(String s, String target) {
        Map<Character, Integer> targetCharCount = new HashMap<>(26);
        for (int i = 0; i < target.length(); ++i) {
            char ch = target.charAt(i);
            targetCharCount.put(ch, targetCharCount.getOrDefault(ch, 0) + 1);
        }
        Map<Character, Integer> sourceCharCount = new HashMap<>(26);
        for (int i = 0; i < s.length(); ++i) {
            char ch = s.charAt(i);
            sourceCharCount.put(ch, sourceCharCount.getOrDefault(ch, 0) + 1);
        }
        int minCnt = Integer.MAX_VALUE;
        for (Character key : targetCharCount.keySet()) {
            //能够组成最多sourceCharCount / targetCharCount个target
            int srcCnt = sourceCharCount.getOrDefault(key, 0);
            int cnt = srcCnt / targetCharCount.get(key);
            minCnt = Math.min(minCnt, cnt);
        }
        return minCnt;
    }

    //p2357
    public int minimumOperations(int[] nums) {
        boolean[] visited = new boolean[101];
        for (int num : nums) {
            visited[num] = true;
        }
        int op = 0;
        for (int i = 1; i <= 100; ++i) {
            if (visited[i]) ++op;
        }
        return op;
    }

    /**
     * 2711【哈希表+计数】对角线上不同值的数量差
     */
    public int[][] differenceOfDistinctValues(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] answer = new int[m][n];
        int i = m - 1, j = 0;
        while (i >= 0 && j < n) {
            Map<Integer, Integer> ltNumCnt = new HashMap<>();
            Map<Integer, Integer> rbNumCnt = new HashMap<>();
            int r = i + 1, c = j + 1;
            while (r < m && c < n) {
                int num = grid[r][c];
                rbNumCnt.put(num, rbNumCnt.getOrDefault(num, 0) + 1);
                ++c;
                ++r;
            }
            answer[i][j] = rbNumCnt.size();
            r = i + 1;
            c = j + 1;
            while (r < m && c < n) {
                int num = grid[r][c], numPrev = grid[r - 1][c - 1];
                int rbCnt = rbNumCnt.get(num) - 1;
                if (0 == rbCnt) rbNumCnt.remove(num);
                else rbNumCnt.put(num, rbCnt);
                ltNumCnt.put(numPrev, ltNumCnt.getOrDefault(numPrev, 0) + 1);
                answer[r][c] = Math.abs(ltNumCnt.size() - rbNumCnt.size());
                ++c;
                ++r;
            }
            if (i > 0) --i;
            else ++j;
        }
        return answer;
    }

    public static void main(String[] args) {
        HashMapSolution solution = new HashMapSolution();
        Assert.isTrue("[[1,1,0],[1,0,1],[0,1,1]]".equals(JsonUtils.toJson(solution.differenceOfDistinctValues(Parser.parse("[[1,2,3],[3,1,5],[3,2,1]]")))));
//        Assert.isTrue(82 == solution.beautySum("abaaababbbaba"));
//        Assert.isTrue(12217 == solution.beautySum("aabkfjjdhfiuefksjdnvsboiuedjhfkfhjdfhsdjfduifheiurbvjhsdxjknmvbdjkncjsdjksnfkjdcbaa"));
//        Assert.isTrue(5 == solution.beautySum("aabcb"));
//        Assert.isTrue(17 == solution.beautySum("aabcbaa"));
//
//        Assert.isTrue(2 == solution.countNicePairs(new int[]{42,11,1,97}));
//        Assert.isTrue(2 == solution.countNicePairs(new int[]{42,11,1,97,210}));
//        Assert.isTrue(4 == solution.countNicePairs(new int[]{13,10,35,24,76}));
//        Assert.isTrue(1 == solution.countNicePairs(new int[]{1,2,30,34,100}));
//
//        Assert.isTrue("[\"daniel\"]".equals(JsonUtils.toJson(solution.alertNames(new String[]{"daniel","daniel","daniel","luis","luis","luis","luis"}, new String[]{"10:00","10:40","11:00","09:00","11:00","13:00","15:00"}))));
//        Assert.isTrue("[\"bob\"]".equals(JsonUtils.toJson(solution.alertNames(new String[]{"alice","alice","alice","bob","bob","bob","bob"}, new String[]{"12:01","12:00","18:00","21:00","21:20","21:30","23:00"}))));
//        Assert.isTrue("[]".equals(JsonUtils.toJson(solution.alertNames(new String[]{"john","john","john"}, new String[]{"23:58","23:59","00:01"}))));
//        Assert.isTrue("[\"clare\",\"leslie\"]".equals(JsonUtils.toJson(solution.alertNames(new String[]{"leslie","leslie","leslie","clare","clare","clare","clare"}, new String[]{"13:00","13:20","14:00","18:00","18:51","19:30","19:49"}))));
//
//        Assert.isTrue("DDDDD!!".equals(solution.alphabetBoardPath("zz")));
//        Assert.isTrue("DDDDD!UUUUURRR!DDDDLLLD!".equals(solution.alphabetBoardPath("zdz")));
//
//        Assert.isTrue(4 == solution.maximalNetworkRank(4, Parser.parse("[[0,1],[0,3],[1,2],[1,3]]")));

//        Assert.isTrue(4 == solution.longestStrChain(new String[]{"a","b","ba","bca","bda","bdca"}));
    }
}
